#include <iostream>
#include <vector>
using namespace std;

/** leetcode中 链表节点的定义
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */


struct ListNode {
    int val;
    ListNode* next;
    ListNode():val(0),next(nullptr) { }
    ListNode(int v):val(v),next(nullptr) { };
    ListNode(int v, ListNode* next):val(v),next(next) {}
};

class Soultion {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 创建一个虚拟头节点，虚拟头节点的next指向head
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        // 定义一个cur节点指针，初始指向虚拟头节点，用于遍历链表
        ListNode*cur = dummyHead;

        while(cur->next != nullptr) {
            if(cur->next->val != val) { // 遍历链表，比较要删除的val是否与节点的值相等
                cur = cur->next;        // 不相等，则跳到下一个节点
            } else {                    // 相等则找到了要删除的节点cur-next
                ListNode* tmp = cur->next; // 保存要删除节点的地址，后续要释放该地址内存
                cur->next = cur->next->next; // 删除操作
                delete tmp; // 释放删除的节点的内存空间
            }
        }

        head = dummyHead->next; // 如果删除的节点是头节点，这步很有必要，从而不要区分头节点和非头节点删除的情况
        delete dummyHead;   // 释放虚拟头节点的内存空间
        return head;    // 返回头节点地址
    }
};

// 创建链表节点函数
ListNode* createNode(int val) {
    return (new ListNode(val)); 
}

// 遍历链表函数
void printList(ListNode* head) {
    ListNode* cur = head;
    cout << "[ " ;
    while(cur) {
        cout << cur->val << "  ";
        cur = cur->next;
    }
    cout << "]";
    cout << endl;
}

int main() {
	ListNode* head = createNode(1);
    ListNode* node1 = createNode(2);
    ListNode* node2 = createNode(6);
    ListNode* node3 = createNode(3);
    ListNode* node4 = createNode(4);
    ListNode* node5 = createNode(5);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    printList(head);

    Soultion s;
    s.removeElements(head, 6);
    printList(head);
}
